/*
N皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入：n = 4
输出：[
  [
    ".Q..",
    "...Q",
    "Q...",
    "..Q."
  ],
  [
    "..Q.",
    "Q...",
    "...Q",
    ".Q.."
  ]
]
解释：如上图所示，4 皇后问题存在两个不同的解法。
*/
/**
 * res 放结果集
 * chessboard[row][col] 存放一种合法方案 row=n;（纵向）col=n;（层）
 * 【终止条件】 row==n;
 * 【剪枝】
 * isvaild检查合法性
 * 【check row：1～row】 因为同层本来就是col 1~n；之前都是检查过的，所以不用【check col】
 * 【check 左上】 row-1~0 col-1~0
 * 【check右上】 row-1~0 col+1~n
 */
var solveNQueens = function(n) {
  const res = [];
  const chessboard = Array(n).fill().map(()=>Array(n).fill('.'));
  const isVaild = (chessboard, row, col)=> {
    //【check row：1～row】 因为同层本来就是col 1~n；之前都是检查过的，所以不用【check col】
    for(let i=0;i<row;i++) {
      if(chessboard[i][col]=='Q') return false;
    }
    //【check 左上】
    for(let i=row-1,j=col-1; i>=0&&j>=0;i--,j--) {
      if(chessboard[i][j]=='Q') return false;
    }
    //【check右上】
    for(let i=row-1,j=col+1; i>=0&&j<n; i--,j++) {
      if(chessboard[i][j]=='Q') return false;
    }
    return true
  };
  const backTrack = (row) => {
    if(row==n) {
      const strBoard = [];
      chessboard.forEach(row=>strBoard.push(row.join(''))); //!结果要符合题意
      res.push(strBoard); 
      return;
    }
    for(let col=0;col<n;col++) {
      if(isVaild(chessboard, row, col)){
        chessboard[row][col] = 'Q'
        backTrack(row+1);
        chessboard[row][col] = '.'
      }else continue;
    }
  }
  backTrack(0);
  return res;
};

const n = 4;
console.log('N皇后',solveNQueens(n));